1. Field of the Invention
The present invention relates to associative memory devices outputting stored data in response to comparison results between input retrieval data and the stored data, and more particularly, to an associative memory device which can change at a software level the length of data being compared, and a variable length code decoding device utilizing the same associative memory device.
2. Description of the Background Art
An associative memory device is known as a memory device which retrieves data having a tag that matches a specific keyword. Such an associative memory device is disclosed, for example, in Japanese Laid-Open Patent No. 10-50076. The associative memory device is configured to compare a part (hereinafter, referred to as a xe2x80x9ctagxe2x80x9d or a xe2x80x9ctag portionxe2x80x9d) of data stored within the device with an input keyword, and to automatically read out data having the tag portion that matches the keyword.
In a conventional associative memory device, however, the data length of the tag portion, or the length of a keyword being compared, has been fixed normally at a hardware level. On the other hand, for data coded employing a variable length coding system, for example, the length of the keyword for comparison cannot necessarily be fixed. Therefore, it is usually difficult to process such data with the associative memory device.
Here, assume that a tag that should be compared is shorter than a data length predetermined at the hardware level, and all the tags stored have the same data length. In such a case, it is possible to fill up every remaining bit of the tag with a specific value and to fix a corresponding bit of the retrieval keyword to the same value, so that a proper retrieval can be conducted.
However, such an approach cannot be utilized for decoding of the variable length code data, because, in the variable length code data, the tag portions to be compared have various data lengths, and the data lengths of the tags cannot be determined before decoding.
Another approach is to modify a data storing method of the associative memory such that a proper retrieval can be conducted whatever value is included in a bit being unused as a tag. For example, assume that an associative memory device having a tag length of 8 bits, which is determined at a hardware level, is being used for retrieval of data having a tag of 6 bits. In such a case, data are stored such that the retrieval can be done without failure whatever values are contained in the remaining 2 bits of the retrieval keyword.
Specifically, a tag originally having 6 bits therein is extended for 2 bits by adding data of xe2x80x9c00xe2x80x9d, xe2x80x9c01xe2x80x9d, xe2x80x9c10xe2x80x9d and xe2x80x9c11xe2x80x9d, respectively, so that four tags with 8 bits each are created based on the one tag with 6 bits. These four tags created are then made to correspond to the same data. In this manner, it becomes possible to conduct proper retrieval even with retrieval data having a length that is shorter than the data length of the tag predetermined at the hardware level.
In such a case, however, it is necessary to create a plurality of (4, in the above-mentioned case) entries with respect to one code. This poses a problem that data storage efficiency is considerably degraded.
An object of the present invention is to provide an associative memory device which is capable of changing the length of a keyword being compared at a software level and also applicable to decoding of a variable-length code efficiently, and to provide a variable-length code decoding device utilizing the same associative memory device.
In summary, the present invention is directed to an associative memory device outputting data according to an input of retrieval data having a plurality of bits, which includes a keyword comparison array and a data storage array.
The keyword comparison array retains a plurality of tag data each having a plurality of bits, and performs matching between the retrieval data input and each of the plurality of tag data. The keyword comparison array includes a plurality of matching circuits provided corresponding to the plurality of tag data, each comparing the retrieval data and corresponding one of the plurality of tag data. Each of the plurality of matching circuits includes: an n number (n is an integer at least 0) of first comparison memory units provided corresponding to n bits of the corresponding tag data, each retaining corresponding one bit and performing a matching operation between the retaining bit and a corresponding bit of the retrieval data; and an m number (m is a natural number) of second comparison memory units provided corresponding to respective parts of remaining bits of the corresponding tag data other than the n bits, each performing the matching operation between corresponding one part of the remaining bits and a corresponding bit of the retrieval data, a matching result of which is invalidated dependent on an externally set comparison condition signal. The keyword comparison array further includes a plurality of matching detection signal lines provided corresponding to the plurality of matching circuits. Each of the plurality of matching detection signal lines has a potential level that is determined according to the matching results of the n number of first comparison memory units and of an (mxe2x88x92k) number (k is an integer from 0 to m) among the m number of second comparison memory units other than the k number thereof having the comparison results invalidated, included in the corresponding matching circuit.
The data storage array responds to the potential level of each of the plurality of matching detection signal lines and outputs data corresponding to one of the plurality of tag data that matches the retrieval data.
Another aspect of the present invention is directed to a variable-length code decoding device for decoding variable-length code data, which includes a retrieval data setting circuit, an associative memory circuit, and a decoding target pointer circuit.
The retrieval data setting circuit receives a bit stream of the variable-length code data input as a decoding target, and outputs retrieval data including a fixed number of bits being decoded in one decoding process.
The associative memory circuit responds to input of the retrieval data, and outputs decoded data corresponding to the variable-length code data and code length data indicating the number of bits of the decoded data. The associative memory circuit includes: a keyword comparison array which retains coded variable-length code data as a plurality of tag data, and performs matching between the retrieval data input and each of the plurality of tag data. The keyword comparison array includes a plurality of matching circuits provided corresponding to the plurality of tag data, each comparing the retrieval data and corresponding one of the plurality of tag data. Each of the plurality of matching circuits has an m number (m is a natural number) of first comparison memory units provided corresponding to respective parts of bits of the corresponding tag data. Each of the first comparison memory units retains corresponding one part of bits and a comparison condition signal externally supplied in advance, and performs a matching operation between the part of bits and a corresponding bit of the retrieval data, a matching result of which is invalidated dependent on the comparison condition signal. The keyword comparison array further includes a plurality of matching detection signal lines provided corresponding to the plurality of matching circuits. Each of the plurality of matching detection signal lines has a potential level that is determined according to the matching results of an (mxe2x88x92k) number (k is an integer from 0 to m) among the m number of the first comparison memory units other than the k number thereof having the matching results invalidated, included in the corresponding matching circuit.
The associative memory circuit further includes a data storage array which, in response to the potential level of each of the plurality of matching detection signal lines, outputs the decoded data and the code length data associated with the variable-length code data corresponding to one of the plurality of tag data.
The decoding target pointer circuit refers to the code-length data and designates to the retrieval data setting circuit a leading bit of the fixed number of bits, out of the bit stream of the variable-length code data input, to be decoded in a next decoding process.
Thus, a primary advantage of the present invention is that it is possible to invalidate, upon matching of each bit between the retrieval data and each tag data, a matching result according to a comparison condition signal in a bit corresponding to the second comparison memory unit. Therefore, it becomes possible to provide an associative memory device that is capable of arbitrarily setting the number of bits being matched between the retrieval data and each tag data, at a software level.
Further, decoding of variable-length code data is performed utilizing an associative memory circuit that is capable of invalidating, upon the matching of each bit between the retrieval data and each tag data, a matching result according to a comparison condition signal in a bit corresponding to the second comparison memory unit. As a result, it becomes possible to efficiently perform the decoding of the variable-length code by arbitrarily setting the number of bits being matched between the retrieval data and each tag data, at a software level.
The foregoing and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.